# -*- coding:utf-8 -*-
from array_stack import Empty


class ArrayQueue:
    """FIFO queue implementation using a Python list class as underlying storage"""

    DEFAULT_CAPACITY = 10

    def __init__(self):
        self._queue = [None] * self.DEFAULT_CAPACITY
        self._size = 0
        self._front = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def first(self):
        if self.is_empty():
            raise Empty("Queue is empty!")
        return self._queue[self._front]

    def enqueue(self, e):
        """Add an element into the back of queue"""
        if self._size == len(self._queue):
            self._resize(len(self._queue) * 2)
        cur = (self._front + self._size) % len(self._queue)
        self._queue[cur] = e
        self._size += 1

    def dequeue(self):
        """Remove and return the first element of queue"""
        if self.is_empty():
            raise Empty("Queue is empty!")
        res = self._queue[self._front]
        self._queue[self._front] = None
        self._front = (self._front + 1) % len(self._queue)
        self._size -= 1
        return res

    def _resize(self, cap):
        """Resize to a new list of capacity >= len(self)"""
        old = self._queue
        walk = self._front
        self._queue = [None] * cap
        for i in range(self._size):
            self._queue[i] = old[walk]
            walk = (walk + 1) % len(old)
        self._front = 0
